import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 03010570
 * @date 2020/07/08
 * describe:    LeetCode : 面试题 16.11 https://leetcode-cn.com/problems/diving-board-lcci/
 */
public class LeetCode_interview_02_01 {

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(3);
        node.next.next.next.next = new ListNode(2);
        node.next.next.next.next.next = new ListNode(1);
        ListNode listNode = removeDuplicateNodes(node);
        while (listNode != null) {
            System.out.print(listNode.val + " , ");
            listNode = listNode.next;
        }

    }

    /**
     *  速度太慢，不推荐
     * 不使用 额外空间， 两次循环搞定
     * 时间复杂度 ： O(N^2)  链表循环遍历两次
     * 空间复杂度 ： O(1)
     *
     * @param head
     * @return
     */
    public static ListNode removeDuplicateNodes(ListNode head) {
        ListNode out = head;
        while (out != null) {
            ListNode in = out;
            while (in.next != null) {
                if (in.next.val == out.val) {
                    in.next = in.next.next;
                } else {
                    in = in.next;
                }
            }
            out = out.next;
        }
        return head;
    }

    /**
     * 方法2 ：基于 方法1的另一种方法 ，HashMap 只使用到了 Key ,改用 HashSet
     * 时间复杂度 ： O(N)
     * 空间复杂度 ： O(N)
     *
     * @param head
     * @return
     */
    public static ListNode removeDuplicateNodes2(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        while (cur.next != null) {
            set.add(cur.val);
            if (set.contains(cur.next.val)) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;

    }

    /**
     * Method 1:
     * 使用哈希表 HashMap
     * 时间复杂度 ： O(N)  遍历一遍
     * 空间复杂度 ： O(N)  额外的空间保存链表
     */
    public static ListNode removeDuplicateNodes1(ListNode head) {
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            map.put(cur.val, cur);
            if (map.get(cur.next.val) != null) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return pre.next;
    }

}
